package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 662.二叉树最大宽度
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。
 * 这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
 *
 * 思路：
 *     将该二叉树的每一个节点进行标号，它的编号==它对应的完全二叉树的编号。
 *     每一层的宽度 = 该层的最右节点编号 - 最左节点的编号 + 1
 */
public class Num_662 {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<NodeWithNum> queue = new LinkedList<>();
        //添加根节点以及编号
        queue.offer(new NodeWithNum(root,1));
        //最大宽度初始化为0
        int maxWidth = 0;
        while(!queue.isEmpty()){
            //当前层的节点数
            int size = queue.size();
            //最左编号为当前层最左边节点的编号
            int leftNum = queue.peek().num;
            //先把最右编号初始化为0
            int rightNum = 0;
            for(int i=0; i<size; i++){
                //弹出队首节点
                NodeWithNum cur = queue.poll();
                //通过循环遍历将最右编号变为当前层的最后一个节点的编号
                rightNum = cur.num;
                if(cur.node.left != null){
                    queue.offer(new NodeWithNum(cur.node.left, cur.num * 2));
                }
                if(cur.node.right != null){
                    queue.offer(new NodeWithNum(cur.node.right, cur.num * 2 + 1));
                }
            }
            maxWidth = Math.max(maxWidth,rightNum - leftNum + 1);
        }
        return maxWidth;
    }
    //写一个内部类，包装二叉树的节点和它的编号
    private class NodeWithNum {
        TreeNode node;
        int num;
        NodeWithNum(TreeNode node,int num){
            this.node = node;
            this.num = num;
        }
    }
}
